# RMQ 区间最值

snippet rmq "Description" b
/* ======== RMQ_BEG */
namespace RMQ_max {
    typedef long long ll; const int siz =30; ll N,f[maxn][siz];

    template <typename T> inline T BEST(T a,T b){ return a > b ? a : b;}
    /*预处理*/ void rmq_init(int size=maxn){N=size;}
    template<typename T> void rmq_init(T size, T a[]){ N=size;for(ll i=1;i<=N;i++) f[i][0] = a[i];}

    void st(){ /*范围*/for(ll j=1;(1<<j)<=N;j++) for(ll i=1;i+(1<<j)-1<=N;i++) f[i][j] = BEST(f[i][j-1],f[i+(1<<(j-1))][j-1]); }

    template<typename T>  //T k =0; while((1<<(k+1)) <= (r-l+1)) k++;
    T query(T l,T r){ T k = T(log(r-l+1)/log(2)); return BEST(f[l][k],f[r-(1<<k)+1][k]); }
}
/* ======== RMQ_END */
endsnippet
